Algorithmes de recherche#

En informatique, un tableau est une structure de données représentant une séquence finie d’éléments auxquels on peut accéder par leur position dans la séquence. On utilisera des listes Python pour représenter ces tableaux. On peut également remarquer qu’une chaîne de caractères est un tableau de caractères.

On s’intéresse dans ce paragraphe à divers algorithmes permettant de traiter des tableaux ou de retrouver de l’information dans ceux-ci.

Recherche d’un élément#

On cherche à savoir si une valeur donnée fait bien partie des éléments d’un tableau. On parcourt tout simplement ce tableau et on renvoie True dès qu’on trouve cette valeur dans le tableau. Si la valeur n’a pas été trouvée à la fin du parcours, on renvoie False.

def appartient(valeur, tableau):
    for element in tableau:
        if element == valeur:
            return True
    return False
appartient('Alice', ['Alice', 'Bob', 'Charles-Antoine'])
True
appartient('Dédé', ['Alice', 'Bob', 'Charles-Antoine'])
False

Note

Le langage Python dispose de l’opérateur in pour déterminer si une valeur appartient à une liste.

'Alice' in ['Alice', 'Bob', 'Charles-Antoine']
True
'Dédé' in ['Alice', 'Bob', 'Charles-Antoine']
False

On peut modifier l’algorithme precédent afin qu’il renvoie l’indice du tableau où on a trouvé la valeur recherché et None si la valeur n’a pas été trouvée.

def indice(valeur, tableau):
    for i in range(len(tableau)):
        if tableau[i] == valeur:
            return i
    return None
indice(2, [5, 4, 1, 2, 3])
3
print(indice(6, [5, 4, 1, 2, 3]))
None

Note

La méthode index de la classe list permet de déterminer l’indice d’une valeur dans une liste.

[5, 4, 1, 2, 3].index(2)
3
[5, 4, 1, 2, 3].index(6)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Input In [10], in <cell line: 1>()
----> 1 [5, 4, 1, 2, 3].index(6)

ValueError: 6 is not in list

Recherche du maximum#

def maximum(tableau):
    m = None
    for element in tableau:
        if m == None or m < element:
            m = element
    return m
maximum([4, 5, 8, 1, 3])
8
print(maximum([]))
None
def argmax(tableau):
    index = None
    for i in range(len(tableau)):
        if index == None or tableau[index] < tableau[i]:
            index = i
    return index
argmax([4, 5, 8, 1, 3])
2
print(argmax([]))
None
def second_maximum(tableau):
    m1 = None
    m2 = None
    for element in tableau:
        if m1 == None or m1 < element:
            m2 = m1
            m1 = element
        elif m2 == None or m2 < element:
            m2 = element
    return m2
second_maximum([4, 5, 8, 1, 3])
5
print(second_maximum([]))
None
print(second_maximum([2]))
None

Comptage des éléments d’un tableau#

def comptage(tableau):
    d = {}
    for element in tableau:
        if element in d:
            d[element] += 1
        else:
            d[element] = 1
    return d
comptage(['Alice', 'Bob', 'Alice', 'Charles', 'Charles', 'Alice'])
{'Alice': 3, 'Bob': 1, 'Charles': 2}

Recherche d’un motif dans une chaîne#

def recherche_motif(motif, chaine):
    n = len(chaine)
    m = len(motif)
    for ind in range(n-m+1):
        nb = 0
        while nb < m and chaine[ind+nb] == motif[nb]:
            nb +=1
        if nb == m:
            return True
    return False
recherche_motif("pipa", "pitapipapa")
True
recherche_motif("tapa", "patapipapa")
False

Recherche des deux valeurs les plus proches d’un tableau#

def plus_proches_valeurs(tableau):
    valeurs = None
    for i in range(len(tableau)):
        for j in range(i+1, len(tableau)):
            if valeurs == None or abs(tableau[i] - tableau[j]) < abs(valeurs[0] - valeurs[1]):
                valeurs = tableau[i], tableau[j]
    return valeurs
plus_proches_valeurs([7, 4, 9, 13])
(7, 9)
print(plus_proches_valeurs([]))
None
print(plus_proches_valeurs([7]))
None

Tri à bulles#

Le tri à bulles fait partie des algorithmes de tri classiques. Trier un tableau consiste à ordonner ses éléments du plus petit au plus grand. On suppose donc que les éléments du tableau sont à valeurs dans un ensemble muni d’une relation d’ordre total.

Le tri à bulles consiste à déplacer les éléments du plus grand au plus petit vers la fin du tableau comme des bulles d’air dans un liquide. Plus précisément :

  • on parcourt le tableau en comparant les couples d’éléments consécutifs ;

  • si deux éléments consécutifs ne sont pas dans le bon ordre, on les échange ;

  • à la fin de ce premiers parcours du tableau, on peut garantir que le plus grand élément du tableau est en dernière position ;

  • on répète alors ce qui précède sur le tableau privé de son dernier élément et ainsi de suite jusqu’à tri complet du tableau.

def tri_bulles(tableau):
    for i in reversed(range(len(tableau))):
        for j in range(i):
            if tableau[j+1] < tableau[j]:
                tableau[j], tableau[j+1] = tableau[j+1], tableau[j]
t = [4, 2, 5, 3, 8, 7, 6, 1]
tri_bulles(t)
t
[1, 2, 3, 4, 5, 6, 7, 8]
t = []
tri_bulles(t)
t
[]
t = [4]
tri_bulles(t)
t
[4]